In storage of secret information, risks of loss or destruction and theft of the secret information have to be considered. The risk of loss or destruction can be reduced by storing a plurality of pieces of secret information. However, this measure increases the risk of theft. A solution to eliminate both risks is a secret sharing scheme (SSS) (see Non-patent literatures 1 and 2, for example).
The secret sharing scheme is a scheme in which a plurality of pieces of share information SH(1), . . . , SH(N) are generated from secret information MSK and shared among and managed by a plurality of share management apparatuses PA(1), . . . , PA(N), and the secret information MSK can be reconstructed only when a predetermined number or more of the pieces of share information SH(1) to SH(N) are obtained. In the following, representative secret sharing schemes will be described.
(N, N) Threshold Secret Sharing Scheme:
According to an (N, N) threshold secret sharing scheme (referred to also as an “N-out-of-N sharing scheme” or “N-out-of-N threshold sharing scheme”), although the secret information MSK can be reconstructed if all the share information SH(1), . . . , SH(N) are given, the secret information MSK cannot be obtained at all when N−1 arbitrary pieces of share information SH(φ1), . . . , share(φN-1) are given. The following is an example of the (N, N) threshold secret sharing scheme.
SH1, . . . , SHN-1 are randomly selected.
SHN=MSK−(SH1+ . . . +SHN-1) is calculated.
Each piece of share information SH1, . . . , SHN is shared among a plurality of share management apparatuses PA(1), . . . , PA(N) for management.
If all the share information SH1, . . . , SHN are given, the secret information MSK can be reconstructed by a reconstruction processing according to MSK=SH1+ . . . +SHN.
The calculation MSK=SH1+ . . . +SHN for reconstructing the secret information MSK from the share information SH1, . . . , SHN is linear. Therefore, if the reconstruction processing is performed for share information SH′(1), . . . , SH′(N) each piece of which is obtained by performing a linear calculation CALC for each piece of share information SH(1), . . . , SH(N) and a value σ as operands, the result of the reconstruction processing is the result of the linear calculation CALC performed for the secret information MSK and the σ as operands. For example, if the reconstruction processing is performed for share information SH′(1)=σ·SH(1), . . . , SH′(N)=σ·SH(N), the following value results.
                                                                                          σ                  ·                                      SH                    ⁡                                          (                      1                      )                                                                      +                …                +                                  σ                  ·                                      SH                    ⁡                                          (                      N                      )                                                                                  =                            ⁢                              σ                ·                                  (                                                            SH                      ⁡                                              (                        1                        )                                                              +                    …                    +                                          SH                      ⁡                                              (                        N                        )                                                                              )                                                                                                        =                            ⁢                                                σ                  ·                  M                                ⁢                                                                  ⁢                S                ⁢                                                                  ⁢                K                                                                        (        1        )            
On the other hand, if the reconstruction processing is performed for share information SH′(1), . . . , SH′(N) each piece of which is obtained by performing a liner calculation CALC for each piece of share information SH(1), . . . , SH(N) and each of independent values σ(1), . . . , σ(N) as operands, in general, the result of a calculation that involves the secret information MSK as an operand cannot be obtained. For example, the reconstruction processing is performed for share information SH′(1)=σ(1)·SH(1), . . . , SH′(N)=σ(N)·SH(N), the following value results.σ(1)·SH(1)+ . . . +σ(N)·SH(N)  (2)
(Kt, N) Threshold Secret Sharing Scheme:
According to a (Kt, N) threshold secret sharing scheme (referred to also as a “Kt-out-of-N sharing scheme” or “Kt-out-of-N threshold secret sharing scheme”), although the secret information MSK can be reconstructed if Kt different arbitrary pieces of share information SH(φ1), . . . , SH(φKt) are given, the secret information MSK cannot be obtained at all if Kt−1 arbitrary pieces of share information SH(φ1), . . . , SH(φKt-1) are given. The subscript “Kt” means Kt. The following is an example of the (Kt, N) threshold secret sharing scheme.
A Kt-1-th order polynomial f(x)=ξ0+ξ1·x+ξ2·x2+ . . . +ξKt-1·xKt-1 that satisfies f(0)=MSK is randomly selected. That is, ξ0=MSK is set, and ξ1, . . . , ξKt-1 are randomly selected. The share information is denoted by SHρ=(ρ, f(ρ)) (ρ=1, . . . , N).
If Kt different arbitrary pieces of share information SH(φ1), . . . , SH(φKt) ((φ1, . . . , φKt)⊂(1, . . . , N)) are obtained, the secret information MSK can be reconstructed by the following reconstruction processing using the Lagrange's interpolation formula, for example.
                              M          ⁢                                          ⁢          S          ⁢                                          ⁢          K                =                              f            ⁡                          (              0              )                                =                                                    λ                1                            ·                              f                ⁡                                  (                                      ϕ                    1                                    )                                                      +            …            +                                          λ                Kt                            ·                              f                ⁡                                  (                                      ϕ                    Kt                                    )                                                                                        (        3        )                                                      λ            ρ                    ⁡                      (            x            )                          =                                                            (                                  x                  -                                      ϕ                    1                                                  )                            ⁢                                                          ⁢                              …                ⁢                                                                  ⁢                                  ⋁                  ρ                                ⁢                                                                  ⁢                …                            ⁢                                                          ⁢                              (                                  x                  -                                      ϕ                                          K                      t                                                                      )                                                                    (                                                      ϕ                    ρ                                    -                                      ϕ                    1                                                  )                            ⁢                                                          ⁢                              …                ⁢                                                                  ⁢                                  ⋁                  ρ                                ⁢                                                                  ⁢                …                            ⁢                                                          ⁢                              (                                                      ϕ                    ρ                                    -                                      ϕ                                          K                      t                                                                      )                                              ∈                                          ⁢                      F            q                                              (        4        )            
Note that
  “      …    ⁢                  ⁢          ⋁      ρ        ⁢                  ⁢    …    ”means that there is not the ρ-th operand from the top [the denominator element (φρ−φρ), the numerator element (x−φρ)]. That is, the denominator of formula (4) is as follows.(φρ−φ1)· . . . ·(φρ−φρ−1)·(φρ−φρ+1)· . . . ·(φρ−φKt)The numerator of formula (4) is as follows.(x−φ1)· . . . ·(x−φρ−1)·(x−φρ+1)· . . . ·(x−φKt)These relations hold on a field.
The calculation expressed by the formula (3) is linear. Therefore, the value reconstructed from the share information SH′(φ1), . . . , SH(φKt) each piece of which is obtained by performing the linear calculation CALC for each piece of share information SH(φ1), . . . , SH(φKt) and the value σ as operands is equal to the result of the linear calculation CALC performed for the secret information MSK and the value σ as operands. On the other hand, if the reconstruction processing is performed for share information SH′(φ1), . . . , SH′(φKt) each piece of which is obtained by performing the liner calculation CALC for each piece of share information SH(φ1), . . . , SH(φKt) and each of independent values σ(φ1), . . . , σ(φKt) as operands, in general, the result of a calculation that involves the secret information MSK as an operand cannot be obtained.